package com.algo.tree;


import org.junit.Test;

//二叉查找树，左节点小于父节点，右节点大于父节点
public class BinarySearchTree {
    private Node root;

    /**
     * 查找节点
     *
     * @param data
     * @return
     */
    public Node find(int data) {
        Node p = root;

        while (p != null) {
            if (data > p.data) {
                p = p.right;
            } else if (data < p.data) {
                p = p.left;
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * 插入节点
     *
     * @param data
     */
    public void insert(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }

        Node p = root;
        while (p != null) {
            if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else if (data < p.data) {
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }
    @Test
    public void test1(){
        Integer i=1000;
        int b=1000;
        System.out.println(i==b);
    }

    /**
     * 删除节点
     */
    public void delete(int data) {
        Node p = root;
        Node pp = null;
        while (p != null) {
            pp = p;
            if (data > p.data) {
                p = p.right;
            } else if (data < p.data) {
                p = p.left;
            }
        }
        if (p == null) return;

        //如果父节点下存在两个节点，找到右子树下最小的节点
        if (pp.left == null && pp.right == null) {
            Node minP = p.right;
            Node minPP = p;
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            p = minP;//在下面删除minP
            pp = minPP;
        }

        //删除的节点只有一个叶子节点或者没有节点
        Node child;
        if (p.left != null) {
            child = p.left;
        } else if (p.right != null) {
            child = p.right;
        } else {
            child = null;
        }

        if (pp == null) {
            root = child;
        } else if (pp.left == p) {
            pp.left = child;
        } else {
            pp.right = child;
        }

    }


    public class Node {
        private int data;
        private Node left;
        private Node right;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

}
